package mao.exaimnation.netease;

/**
 * @author Totoro
 * @date 2020/8/17
 * @explain:  注意看限制条件。
 * 给出n个物品和它对应的价值，可以舍弃几件物品，现在要将物品分给两个人，
 * 两个人得到的物品数量可以不一样，但是得到的价值必须是一样的，
 * 问最少可以舍弃多少价值的物品？
 * 输入为T（有多少组案例），n（物品数量），a（有n个数字，a[i]表示第i个物品的价值）。
 * 输出为一个数字，表示最少可以丢弃的物品价值。
 * 如对于案例输入：
 * 1
 * 5
 * 30    60    5    15    30
 * 输出应为：
 * 20
 * 即应该丢弃价值为5和15的物品，然后将剩下的物品平分给两个人。
 * 因为声明给出的n<=15，因此大佬们都表示暴力法可以ac。思路为：对于每一件物品，
 * 都会存在三种选择：1、给第一个人。2、给第二个人。3、舍弃这件物品。
 * 所以可以将问题转化为树，进行深度优先搜索，只需要搜索时寻找到达最后一件物品时，
 * 两个人手里物品的价值相同，并且找到舍弃价值最小的那一个节点即可。
 */
public class Main3 {
}
